
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1232. -- [Usaco2008Nov]安慰奶牛cheer -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1232: [Usaco2008Nov]安慰奶牛cheer</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>322&nbsp;&nbsp;<span class=green>Solved: </span>219<br>[<a href='submitpage.php?id=1232'>Submit</a>][<a href='problemstatus.php?id=1232'>Status</a>][<a href='bbs.php?id=1232'>Discuss</a>]</center><h2>Description</h2><div class=content>
Farmer John变得非常懒, 他不想再继续维护供奶牛之间供通行的道路. 道路被用来连接N
(5 <= N <= 10,000)个牧场, 牧场被连续地编号为1..N. 每一个牧场都是一个奶牛的家.
FJ计划除去P(N-1 <= P <= 100,000)条道路中尽可能多的道路, 但是还要保持牧场之间
的连通性. 你首先要决定那些道路是需要保留的N-1条道路.

第j条双向道路连接了牧场S_j和E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j),
而且走完它需要L_j (0 <= L_j <= 1,000)的时间. 没有两个牧场是被一条以上的道路所连接.

奶牛们非常伤心, 因为她们的交通系统被削减了. 你需要到每一个奶牛的住处去安慰她们. 每次
你到达第i个牧场的时候(即使你已经到过), 你必须花去C_i (1 <= C_i <= 1,000)的
时间和奶牛交谈.

你每个晚上都会在同一个牧场(这是供你选择的)过夜, 直到奶牛们都从悲伤中缓过神来. 在早上
起来和晚上回去睡觉的时候, 你都需要和在你睡觉的牧场的奶牛交谈一次. 这样你才能完成你的
交谈任务.

假设Farmer John采纳了你的建议, 请计算出使所有奶牛都被安慰的最少时间.

对于你前10次的提交, 你的程序会在一部分正式的测试数据上运行, 并且返回运行的结果.


程序名: cheer

</div><h2>Input</h2><div class=content>* 第 1 行: 用空格隔开的两个整数N和P
* 第 2..N+1 行: 第i+1行包含了一个整数: C_i
* 第 N+2..N+P+1 行: 第 N+j+1 行包含用空格隔开的三个整数: S_j, E_j 和 L_j
</div><h2>Output</h2><div class=content>第 1 行: 一个整数, 所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间).
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>5 7<br />
10<br />
10<br />
20<br />
6<br />
30<br />
1 2 5<br />
2 3 5<br />
2 4 12<br />
3 4 17<br />
2 5 15<br />
3 5 6<br />
4 5 12<br />
<br />
输入解释:<br />
<br />
              +-(15)-+<br />
             /        \<br />
            /          \<br />
     1-(5)-2-(5)-3-(6)--5<br />
            \   /(17)  /<br />
         (12)\ /      /(12)<br />
              4------+<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>176<br />
输出解释:<br />
<br />
保持这些路径:<br />
<br />
     1-(5)-2-(5)-3      5<br />
            \          /<br />
         (12)\        /(12)<br />
             *4------+<br />
<br />
从牧场4起床, 然后按照 4, 5, 4, 2, 3, 2, 1, 2, 4 的顺序来访问奶牛们, 总共<br />
需要176个单位的时间.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1232'>Submit</a>][<a href='problemstatus.php?id=1232'>Status</a>][<a href='bbs.php?id=1232'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
